//https://leetcode.cn/problems/substring-with-concatenation-of-all-words/submissions/550935384/

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> hash1;
        for (auto& s : words)
        {
            hash1[s]++;
        }
        int len = words[0].size(), m = words.size();
        vector<int> v;
        for (size_t i = 0; i < len; i++)
        {
            unordered_map<string, int> hash2;
            for (int left = i, right = i, count = 0; right + len <= s.size(); right += len)
            {
                string in = s.substr(right, len);
                //进窗口
                if (hash1.count(in) && (++hash2[in]) <= hash1[in]) count++;
                //判断条件
                while (right - left + 1 > m * len)
                {
                    //出窗口
                    string out = s.substr(left, len);
                    if (hash1.count(out) && (hash2[out]--) <= hash1[out]) count--;
                    left += len;
                }
                //更新结果
                if (count == m)
                    v.push_back(left);
            }
        }

        return v;
    }
};